package org.laizili.solution.leetcode;

import org.laizili.structure.tree.bitree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
 * <a href="https://leetcode-cn.com/problems/binary-tree-preorder-traversal/">144. 二叉树的前序遍历<a/>
 * <p>
 * tags: 栈; 递归
 * </p>
 */
public class Problem144 {
    // 非递归前序遍历
    private static class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> path = new ArrayDeque<>();
            while (root != null || !path.isEmpty()) {
                if (root != null) {
                    res.add(root.val);
                    path.push(root);
                    root = root.left;
                } else {
                    root = path.pop().right;
                }
            }
            return res;

        }
    }
}
